#include "NoMergeTreeFunction.hpp"
#include "HuffmanTreeFunction.hpp"
#include <fstream>
#include <cstdint>

using namespace std;

// 尾插法插入至权重链表
void insertHelpNode(HelpNode *list, int data) {
    HelpNode *node = list->next;
    auto *newHelpNode = new HelpNode;
    newHelpNode->data = data;
    newHelpNode->next = nullptr;
    if (node == nullptr) {
        list->next = newHelpNode;
        list->data++;
        return;
    }
    while (node->next != nullptr) {
        node = node->next;
    }
    list->data++;
    node->next = newHelpNode;
}

// 从权重链表中查找最小值
int getMin(HelpNode *list) {
    if (list->data <= 0) {
        return -1;
    }
    HelpNode *node = list->next;
    // 记录位置
    int minIndex = 1;
    int min = INT32_MAX;
    for (int i = 0; node != nullptr; i++, node = node->next) {
        if (node->data < min) {
            min = node->data;
            minIndex = i;
        }
    }
    // 删除节点
    if (minIndex == 0) {
        HelpNode *delNode = list->next;
        list->next = delNode->next;
        delete delNode;
    } else {
        // 第一个节点
        node = list->next;
        for (int i = 1; i <= minIndex - 1; i++) {
            node = node->next;
        }
        HelpNode *delNode = node->next;
        node->next = delNode->next;
        delete delNode;
    }
    list->data--;
    return min;
}

// 生成权重链表
HelpNode *getHelpList(int arr[], int size) {
    auto *list = new HelpNode;
    list->next = nullptr;
    list->data = 0;
    for (int i = 0; i < size; i++) {
        // 插入
        insertHelpNode(list, arr[i]);
    }
    return list;
}

// 获取权重链表的长度

// 创建父节点()
Node *mergeTree0(int left, int right) {
    Node *fatherNode = new Node;

    Node *leftNode = new Node;
    leftNode->data = left;
    leftNode->left = nullptr;
    leftNode->right = nullptr;

    Node *rightNode = new Node;
    rightNode->data = right;
    rightNode->left = nullptr;
    rightNode->right = nullptr;

    fatherNode->data = left + right;
    fatherNode->left = leftNode;
    fatherNode->right = rightNode;
    return fatherNode;
}

Node *mergeTree1RightNode(int left, Node *rightNode) {
    Node *fatherNode = new Node;

    Node *leftNode = new Node;
    leftNode->data = left;
    leftNode->left = nullptr;
    leftNode->right = nullptr;

    fatherNode->data = left + rightNode->data;
    fatherNode->left = leftNode;
    fatherNode->right = rightNode;
    return fatherNode;
}

Node *mergeTree1LeftNode(Node *leftNode, int right) {
    Node *fatherNode = new Node;

    Node *rightNode = new Node;
    rightNode->data = right;
    rightNode->left = nullptr;
    rightNode->right = nullptr;

    fatherNode->data = leftNode->data + right;
    fatherNode->left = leftNode;
    fatherNode->right = rightNode;
    return fatherNode;
}

Node *mergeTree2(Node *leftNode, Node *rightNode) {
    Node *fatherNode = new Node;
    fatherNode->data = leftNode->data + rightNode->data;
    fatherNode->left = leftNode;
    fatherNode->right = rightNode;
    return fatherNode;
}

// 生成哈夫曼树
Node *createHuffmanTree(HelpNode *helpList) {
    // 用于存放未合并的树
    NoMergeTreeList *noMergeTreeList = initNoMergeTreeList();

    // 表示还没有合并完
    while (helpList->data > 1) {
        int min_first = getMin(helpList);
        int min_second = getMin(helpList);
        // 插入二者的和
        insertHelpNode(helpList, min_first + min_second);

        // 匹配
        Result *result = match(noMergeTreeList, min_first, min_second);

        int count = result->count;

        // 合并
        if (count == 0) {
            // 如果最小值不存在于任何未合成树
            insertNoMergeTree(noMergeTreeList, mergeTree0(min_first, min_second));
        } else if (count == 1) {
            // 仅最小匹配 使用leftNode
            insertNoMergeTree(noMergeTreeList, mergeTree1LeftNode(result->firstTree, min_second));
        } else if (count == 2) {
            // 仅第二小匹配 使用rightNode
            insertNoMergeTree(noMergeTreeList, mergeTree1RightNode(min_first, result->secondTree));
        } else {
            // 两个都匹配
            insertNoMergeTree(noMergeTreeList, mergeTree2(result->firstTree, result->secondTree));
        }
    }
    // 最后一个节点
    return noMergeTreeList->next->noMergeTree;
}

// 获取权重数组
void getNumArr(Code arr[], int numArr[], int size) {
    for (int i = 0; i < size; i++) {
        numArr[i] = arr[i].weight;
    }
}

// 写入哈夫曼编码
void codeTree(Code arr[], Node *huffmanTree, int size, const string& code) {
    const string& str = code;
    string strLeft = code;
    string strRight = code;

    if (huffmanTree->left == nullptr && huffmanTree->right == nullptr)
        for (int i = 0; i < size; i++) {
            if (huffmanTree->data == arr[i].weight && !arr[i].isMatched) {
                arr[i].decode = str;
                arr[i].isMatched = true;
                break;
            }
        }

    if (huffmanTree->left != nullptr) {
        codeTree(arr, huffmanTree->left, size, strLeft += "0");
    }
    if (huffmanTree->right != nullptr) {
        codeTree(arr, huffmanTree->right, size, strRight += "1");
    }
}

// 写入文件
// 二进制文件格式：
// 1B character , 4B weight , 1B isMatched ,
// 4B decodeLength , ${decodeLength}B decode
void writeToFile(Code arr[], int size) {
    ofstream codeBook;
    codeBook.open("hfmTree.dat", ios::out | ios::binary);
    for (int i = 0; i < size; i++) {
        Code code = arr[i];
        // 写入 character
        codeBook.write(&code.character, sizeof(char));
        // 写入 weight
        codeBook.write(reinterpret_cast<char *>(&code.weight), sizeof(int));
        // 写入 isMatched
        codeBook.write(reinterpret_cast<char *>(&code.isMatched), sizeof(bool));
        // 写入decode
        // 获取decode长度
        int decodeLength = code.decode.length();
        // 写入长度
        codeBook.write(reinterpret_cast<char *>(&decodeLength), sizeof(int));
        // 写入decode
        codeBook.write(code.decode.c_str(), decodeLength);
    }
    codeBook.close();
    ofstream hfmTreeSize;
    hfmTreeSize.open("hfmTreeSize.dat");
    hfmTreeSize << size;
    hfmTreeSize.close();
}

// 获取数组大小
int getHfmTreeSize() {
    int size = 0;
    ifstream hfmTreeSize;
    hfmTreeSize.open("hfmTreeSize.dat", ios::binary);
    hfmTreeSize >> size;
    hfmTreeSize.close();
    return size;
}

// 读取文件
void readFromFile(Code arr[], int size) {
    ifstream codeBook;
    codeBook.open("hfmTree.dat", ios::in | ios::binary);
    for (int i = 0; i < size; i++) {
        Code *code = arr + i;
        // 读取 character
        codeBook.read(&code->character, sizeof(char));
        // 读取 weight
        codeBook.read(reinterpret_cast<char *>(&code->weight), sizeof(int));
        // 获取 isMatched
        codeBook.read(reinterpret_cast<char *>(&code->isMatched), sizeof(bool));
        // 获取长度
        int decodeLength = 0;
        codeBook.read(reinterpret_cast<char *>(&decodeLength), sizeof(int));
        // 重新分配decode大小
        code->decode.resize(decodeLength);
        // 写入decode
        codeBook.read(&code->decode[0], decodeLength);
    }
    codeBook.close();
}

// 字符转码
void encode(Code arr[], char character, int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i].character == character) {
            cout << arr[i].decode << endl;
            return;
        }
    }
    cout << "No decode matched" << endl;
}

// 码转字符
char decode(Code arr[], string decode, int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i].decode == decode) {
            return arr[i].character;
        }
    }
    cout << "No decode matched" << endl;
    return '\0';
}

// 打印二叉树:   type : 0表示根节点，１表示左节点，２表示右节点. level表示层次，用于控制显示的距离
void printTree(Node *huffmanTree, int type, int level) {
    int i;

    if (nullptr == huffmanTree)
        return;

    printTree(huffmanTree->right, 2, level + 1);
    switch (type) {
        case 0:
            printf("%2d\n", huffmanTree->data);
            break;
        case 1:
            for (i = 0; i < level; i++)
                printf("\t");
            printf("\\ %2d\n", huffmanTree->data);
            break;
        case 2:
            for (i = 0; i < level; i++)
                printf("\t");
            printf("/ %2d\n", huffmanTree->data);
            break;
    }
    printTree(huffmanTree->left, 1, level + 1);
}
